De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat

vragen bekijken

een vraag stellen

hulpjes

zoeken

FAQ

links

twitter

boeken

help

inloggen

colofon

Reageren...

Re: Casio 9850 breuken vervolg

We hebben opgemerkt dat voor een graaf g een ondergrens voor X(G) kunnen vinden door te zoeken naar de grootste volledige deelgraaf Kn in G.
Kunnen we ook iets zeggen over een bovengrens voor X(G). Jazeker, toon aan dat bovengrens gegeven wordt met [1 + maximale valentie].

Kan iemand mij helpen met bovenstaande vraag?

Alvast bedankt!

Groeten

Antwoord

Laten we is uitgaan van het 'worst case scenario': de complete graaf (ook wel clique genoemd). In een clique zijn alle knopen verbonden met elkaar maar niet met zichzelf*, dus hebben alle knopen een andere kleur. Het chromatisch getal (X(G)) van een clique is dus gelijk aan het aantal knopen N. De maximale valentie ($
\Delta
$N) van een complete graaf met N knopen is N-1 (want knopen zijn niet met zichzelf verbonden).

Aangezien X(G) = N en $
\Delta
$N = N-1 is eenvoudig te zien dat X(G) = $
\Delta
$N + 1

Het is niet denkbaar dat een graaf meer kleuren nodig heeft dan knopen, dus dit is het absolute maximum voor X(G).

*=Voor een graaf waarvan de knopen ook met zichzelf zijn verbonden is het chromatisch getal niet te bepalen en ook niet informatief.

Ter (overbodige) informatie:
Volgens Brook's theorema geldt dat voor alle grafen behalve complete grafen en cyclische grafen met een oneven aantal knopen het aantal kleuren gelijk is aan de maximale valentie, dus: X(G) = $
\Delta
$N.

Gebruik dit formulier alleen om te reageren op de inhoud van de vraag en/of het antwoord hierboven. Voor het stellen van nieuwe vragen kan je gebruik maken van een vraag stellen in het menu aan de linker kant. Alvast bedankt!

Reactie:
	Klik eerst in het tekstvlak voordat je deze knopjes en tekens gebruikt. Pas op: onderstaande knopjes en speciale karakters werken niet bij ALLE browsers! áâæàåãäßçéêèëíîìïñóôòøõöúûùüýÿ½¼¾€£®© $\forall$$\exists$$\neg$$\wedge$$\vee$$\Leftrightarrow$$\Leftarrow$$\Rightarrow$$\emptyset$$\cap$$\cup$$\supset$$\supseteq$$\not\subset$$\subset$$\subseteq$$\in$$\notin$ $\sim$$\equiv$$\ne$$\pm$$\times$$\div$$\otimes$$\oplus$$\pi$$\leftarrow$$\uparrow$$\to$$\downarrow$ $\sqrt{}$$\sum$$\prod$$\infty$$\smallint$$\Delta$$\nabla$$\partial$$\angle$$\bot$$\cong$$\widehat p$ $\alpha$$\beta$$\gamma$$\delta$$\varepsilon$$\phi$$\theta$$\lambda$$\mu$$\rho$$\sigma$$\tau$$\omega$$\chi$$\Gamma$$\vartheta$$\Lambda$$\Omega$$\Psi$$\zeta$ $\mathbf{N}$ $\mathbf{Z}$ $\mathbf{Q}$ $\mathbf{R}$ $\mathbf{C}$
Categorie:	Rekenmachine
Ik ben:	-------------- Maak een keuze --------------- Leerling onderbouw vmbo-havo-vwo Leerling bovenbouw vmbo Leerling bovenbouw havo-vwo Leerling mbo Student hbo Student universiteit 1ste graad ASO-TSO-BSO Overige TSO-BSO 2de graad ASO 3de graad ASO Student Hoger Onderwijs België Student universiteit België Cursist vavo Docent Ouder Iets anders Beantwoorder
Naam:
Emailadres:
Datum:	19-5-2024